package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 这不一个 dfs 就搞定的东西吗？
 * */
public class _17_12_tree {
    
    class good {
        public TreeNode convertBiNode(TreeNode root) {
            dfs(root);
            return head;
        }
        TreeNode prev, head;
        void dfs(TreeNode root) {
            if (root == null) return;
            dfs(root.left);
            if (prev == null) head = root;
            else {
                prev.right = root;
                root.left = null;
            }
            prev = root;
            dfs(root.right);
        }
    }
    
    class dummy_head {
        TreeNode head = new TreeNode(0);
        TreeNode prev = head;
        public TreeNode convertBiNode(TreeNode root) {
            dfs(root);
            return head.right;
        }
        void dfs(TreeNode root) {
            if (root == null) return;
            dfs(root.left);
            root.left = null;
            prev.right = root;
            prev = root;
            dfs(root.right);
        }
    }
    
    // 迭代法，很熟悉了，还是得写写，不要眼高手低
    // 有点慢！5ms
    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) return null;
        TreeNode head = new TreeNode(0);
        TreeNode prev = head;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                node.left = null;
                prev.right = node;
                prev = node;
                root = node.right;
            }
        }
        return head.right;
    }
    
}
